#pragma once

#include <queue>
#include <map>
#include <set>
#include "msli/common/utils.h"

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 哈夫曼树节点类
template<typename T>
class HuffmanTreeNode {
public:
    bool isLeaf{};
    HuffmanTreeNode *left, *right, *parent;

    Point<T> point;
    DIS_TYPE radius{};
    OID_TYPE leafCount{};

    // 初始化叶节点
    explicit HuffmanTreeNode(const Point<T> &p) :
            isLeaf(true), left(nullptr), right(nullptr), point(p), radius(0.0), leafCount(1) {}

    // 初始化非叶节点
    explicit HuffmanTreeNode(const Point<T> &p, HuffmanTreeNode<T> *l, HuffmanTreeNode<T> *r, DIS_TYPE radius,
                             OID_TYPE leafCount) :
            isLeaf(false), left(l), right(r), point(p), radius(radius), leafCount(leafCount) {}
};

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 从哈夫曼树中收集符合要求的节点并先按层级排序再按单价排序类
template<typename T>
class TempNode {
public:
    int level;
    double collectionGuidelines;   // 可以是面积,单价
    OID_TYPE leafCount{};
    HuffmanTreeNode<T> *huffmanTreeNode;

    TempNode(int level, double gl, OID_TYPE lC, HuffmanTreeNode<T> *hTN) : level(level), collectionGuidelines(gl),
                                                                           leafCount(lC),
                                                                           huffmanTreeNode(hTN) {}

    // 按单价升序排序
    static bool compareByGuidelines(const TempNode<T> &node1, const TempNode<T> &node2) {
        return node1.collectionGuidelines < node2.collectionGuidelines;
    }

    // 先按层级排序, 层级相同再按数量排序
    static bool compareByLevelAndLeafCount(const TempNode<T> &node1, const TempNode<T> &node2) {
        if (node1.level < node2.level) {
            return true;
        } else if (node1.level == node2.level) {
            return node1.leafCount < node2.leafCount;
        }
        return false;
    }
};

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 哈夫曼树类
template<typename T>
class HuffmanTree {
private:
    HuffmanTreeNode<T> *root;
public:
    HuffmanTreeNode<T> *getRoot() const {
        return root;
    }

    explicit HuffmanTree() : root(nullptr) {}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // 递归删除树中的节点
    void deleteTree(HuffmanTreeNode<T> *node) {
        if (node) {
            deleteTree(node->left);   // 删除左子树
            deleteTree(node->right);  // 删除右子树
            delete node;              // 删除当前节点
        }
    }

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // 析构函数：递归删除树中的节点
    ~HuffmanTree() {
        deleteTree(getRoot());  // 删除根节点及其子节点
    }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
private:
    double calculateCircleArea(DIS_TYPE radius) {
        return 3.141592653589793 * radius * radius;
    }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public:
    // 辅助函数：收集内节点覆盖的所有叶节点
    void collectLeafPoints(HuffmanTreeNode<T> *node, std::vector<Point<T>> &leafPoints) {
        if (node->isLeaf) {
            leafPoints.push_back(node->point);
        } else {
            collectLeafPoints(node->left, leafPoints);
            collectLeafPoints(node->right, leafPoints);
        }
    }

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
private:
    // 计算树高
    int getTreeHeight(HuffmanTreeNode<T> *node) {
        if (node == nullptr) {
            return 0;
        }

        // 返回左右子树中较大的高度加1（加上根节点这一层）
        return std::max(getTreeHeight(node->left), getTreeHeight(node->right)) + 1;
    }

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // 判断内部节点是否有效
    bool isMergeValid(HuffmanTreeNode<T> *node1, HuffmanTreeNode<T> *node2) {
        // 如果正在合并的两个节点均是内节点，则可以合并
        if (!node1->isLeaf && !node2->isLeaf) {
            return true;
        }

        // 如果叶节点数量不超过 inner_Max,则节点有效
        if ((node1->leafCount + node2->leafCount) > LEAF_MUN_MAX)
            return false;

        return true;
    }

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // 最小堆构建哈夫曼树
    void minHeapBuildHuffmanTree(std::priority_queue<Edge, std::vector<Edge>, std::greater<>> &minHeap,
                                 std::vector<HuffmanTreeNode<T> *> &queue_old_nodes,
                                 std::vector<HuffmanTreeNode<T> *> &queue_new_nodes) {
        // 构建哈夫曼树
        while (!minHeap.empty()) {
            Edge nearest = minHeap.top();
            minHeap.pop();

            // 距离最近的两个节点
            OID_TYPE minDisIndex1 = nearest.point1_id, minDisIndex2 = nearest.point2_id;

            if (!queue_old_nodes[minDisIndex1] || !queue_old_nodes[minDisIndex2]) continue; // 已合并的节点跳过
            ////////////////////////////////////////////////////////////////////////////////////////////////////////////
            // 判断是否可以进行合并：不能则加入 new 队列待合并
            if (!isMergeValid(queue_old_nodes[minDisIndex1], queue_old_nodes[minDisIndex2])) {
                if (!queue_old_nodes[minDisIndex1]->isLeaf) {
                    queue_new_nodes.push_back(queue_old_nodes[minDisIndex1]);
                    queue_old_nodes[minDisIndex1] = nullptr;
                    continue;
                }

                if (!queue_old_nodes[minDisIndex2]->isLeaf) {
                    queue_new_nodes.push_back(queue_old_nodes[minDisIndex2]);
                    queue_old_nodes[minDisIndex2] = nullptr;
                    continue;
                }
            }
            ////////////////////////////////////////////////////////////////////////////////////////////////////////////
            // 合并两个节点
            OID_TYPE leafCount = queue_old_nodes[minDisIndex1]->leafCount + queue_old_nodes[minDisIndex2]->leafCount;

            if (queue_old_nodes[minDisIndex1]->isLeaf) {
                DIS_TYPE radius = queue_old_nodes[minDisIndex1]->point.distance(queue_old_nodes[minDisIndex2]->point) +
                                  queue_old_nodes[minDisIndex2]->radius;

                auto *newNode = new HuffmanTreeNode<T>(queue_old_nodes[minDisIndex1]->point,
                                                       queue_old_nodes[minDisIndex1], queue_old_nodes[minDisIndex2],
                                                       radius, leafCount);

                queue_old_nodes[minDisIndex1]->parent = newNode;
                queue_old_nodes[minDisIndex2]->parent = newNode;

                // 维护新旧队列
                queue_old_nodes[minDisIndex1] = newNode;
                queue_old_nodes[minDisIndex2] = nullptr;
            } else {
                DIS_TYPE radius = queue_old_nodes[minDisIndex2]->point.distance(queue_old_nodes[minDisIndex1]->point) +
                                  queue_old_nodes[minDisIndex1]->radius;

                auto *newNode = new HuffmanTreeNode<T>(queue_old_nodes[minDisIndex2]->point,
                                                       queue_old_nodes[minDisIndex2], queue_old_nodes[minDisIndex1],
                                                       radius, leafCount);

                queue_old_nodes[minDisIndex1]->parent = newNode;
                queue_old_nodes[minDisIndex2]->parent = newNode;

                // 维护新旧队列
                queue_old_nodes[minDisIndex2] = newNode;
                queue_old_nodes[minDisIndex1] = nullptr;
            }

            // 将新队列中的节点合并到老队列,并维护新边
            int tempSize = queue_new_nodes.size();
            if (tempSize >= 2) {
                for (int i = 0; i < tempSize; ++i) {
                    queue_old_nodes[queue_new_nodes[i]->point.id] = queue_new_nodes[i];

                    for (int j = i + 1; j < tempSize; ++j) {
                        DIS_TYPE dist = queue_new_nodes[i]->point.distance(queue_new_nodes[j]->point);
                        minHeap.push({dist, queue_new_nodes[i]->point.id, queue_new_nodes[j]->point.id});
                    }
                }

                queue_new_nodes.clear();
            }
        }
    }

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // 构建哈夫曼树的辅助函数============堆优化复杂度也是 N^2 logN
    HuffmanTreeNode<T> *buildHuffmanTree(const std::vector<Point<T>> &points, uint64_t DATASIZE) {

        std::priority_queue<Edge, std::vector<Edge>, std::greater<>> minHeap;   // 最小堆
        std::vector<HuffmanTreeNode<T> *> queue_old_nodes(DATASIZE);
        std::vector<HuffmanTreeNode<T> *> queue_new_nodes;

        // 计算所有点对的初始距离并构建叶节点
        for (int i = 0; i < DATASIZE; ++i) {
            auto *leaf = new HuffmanTreeNode<T>(points[i]);
            if (points[i].id < DATASIZE) {
                queue_old_nodes[points[i].id] = leaf;
            } else {
                throw std::runtime_error("最近点对构建时，数组下标越界！！！");
            }

            for (int j = i + 1; j < DATASIZE; ++j) {
                DIS_TYPE dist = points[i].distance(points[j]);
                minHeap.push({dist, points[i].id, points[j].id});
            }
        }

        minHeapBuildHuffmanTree(minHeap, queue_old_nodes, queue_new_nodes);
        ////////////////////////////////////////////////////////////////////////////////////////////////////////////////
        std::vector<HuffmanTreeNode<T> *> NotNullQueue;

        return dfsClearQueueOldNodes(queue_old_nodes, NotNullQueue, minHeap);
    }

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    HuffmanTreeNode<T> *dfsClearQueueOldNodes(std::vector<HuffmanTreeNode<T> *> &queue_old_nodes,
                                              std::vector<HuffmanTreeNode<T> *> &NotNullQueue,
                                              std::priority_queue<Edge, std::vector<Edge>, std::greater<>> &minHeap) {

        uint32_t noNullCount = queueOldNodesNotNullCounts(queue_old_nodes, NotNullQueue);

        if (noNullCount == 1) {
            return NotNullQueue[0];
        }

        ClearQueueOldNodes(queue_old_nodes, NotNullQueue, noNullCount, minHeap);

        NotNullQueue.clear();
        dfsClearQueueOldNodes(queue_old_nodes, NotNullQueue, minHeap);
    }


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    uint32_t queueOldNodesNotNullCounts(std::vector<HuffmanTreeNode<T> *> &queue_old_nodes,
                                        std::vector<HuffmanTreeNode<T> *> &NotNullQueue) {

        uint32_t noNullCount = 0;
        for (auto &node: queue_old_nodes) {
            if (node) {
                noNullCount++;
                NotNullQueue.push_back(node);
            }
        }

        return noNullCount;
    }

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // 递归清空老队列构建出根节点
    void ClearQueueOldNodes(std::vector<HuffmanTreeNode<T> *> &queue_old_nodes,
                            std::vector<HuffmanTreeNode<T> *> &NotNullQueue, uint32_t noNullCount,
                            std::priority_queue<Edge, std::vector<Edge>, std::greater<>> &minHeap) {

        for (int i = 0; i < noNullCount; ++i) {
            for (int j = i + 1; j < noNullCount; ++j) {
                DIS_TYPE dist = NotNullQueue[i]->point.distance(NotNullQueue[j]->point);
                minHeap.push({dist, NotNullQueue[i]->point.id, NotNullQueue[j]->point.id});
            }
        }

        while (!minHeap.empty()) {
            Edge nearest = minHeap.top();
            minHeap.pop();

            // 距离最近的两个节点
            OID_TYPE minDisIndex1 = nearest.point1_id, minDisIndex2 = nearest.point2_id;

            if (!queue_old_nodes[minDisIndex1] || !queue_old_nodes[minDisIndex2]) continue;
            ////////////////////////////////////////////////////////////////////////////////////////////////////////////
            // 合并两个节点
            OID_TYPE leafCount = queue_old_nodes[minDisIndex1]->leafCount + queue_old_nodes[minDisIndex2]->leafCount;

            if (queue_old_nodes[minDisIndex1]->isLeaf) {
                DIS_TYPE radius = queue_old_nodes[minDisIndex1]->point.distance(queue_old_nodes[minDisIndex2]->point) +
                                  queue_old_nodes[minDisIndex2]->radius;

                auto *newNode = new HuffmanTreeNode<T>(queue_old_nodes[minDisIndex1]->point,
                                                       queue_old_nodes[minDisIndex1], queue_old_nodes[minDisIndex2],
                                                       radius, leafCount);

                queue_old_nodes[minDisIndex1]->parent = newNode;
                queue_old_nodes[minDisIndex2]->parent = newNode;

                // 维护新旧队列
                queue_old_nodes[minDisIndex1] = newNode;
                queue_old_nodes[minDisIndex2] = nullptr;
            } else {
                DIS_TYPE radius = queue_old_nodes[minDisIndex2]->point.distance(queue_old_nodes[minDisIndex1]->point) +
                                  queue_old_nodes[minDisIndex1]->radius;

                auto *newNode = new HuffmanTreeNode<T>(queue_old_nodes[minDisIndex2]->point,
                                                       queue_old_nodes[minDisIndex2], queue_old_nodes[minDisIndex1],
                                                       radius, leafCount);

                queue_old_nodes[minDisIndex1]->parent = newNode;
                queue_old_nodes[minDisIndex2]->parent = newNode;

                // 维护新旧队列
                queue_old_nodes[minDisIndex2] = newNode;
                queue_old_nodes[minDisIndex1] = nullptr;
            }
        }
    }

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public:
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // 构建哈夫曼树
    void build(const std::vector<Point<T>> &points, uint64_t DATASIZE) {
        root = buildHuffmanTree(points, DATASIZE);
    }

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // 计算树高
    int getHeight() {
        auto curRoot = getRoot();
        if (curRoot == nullptr) {
            return 0;
        }
        return getTreeHeight(curRoot);
    }

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // 广度优先遍历哈夫曼树内节点并输出信息
    void bfsTraverseHuffmanTree() {
        auto curRoot = getRoot();
        if (curRoot == nullptr) {
            return;
        }
        std::queue<HuffmanTreeNode<T> *> q;
        q.push(curRoot);
        while (!q.empty()) {
            HuffmanTreeNode<T> *node = q.front();
            q.pop();
            if (!node->isLeaf) {
                std::cout << "Inner Node - Center: (" << node->point.coords[0] << ", "
                          << node->point.coords[1]
                          << "), Radius: "
                          << node->radius << ", Leaf Count: " << node->leafCount << std::endl;
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            } else {
                std::cout << "Leaf Node: OID: " << node->point.id << " 前两维坐标 < " << node->point.coords[0]
                          << ", " << node->point.coords[1] << "> " << std::endl;
            }
        }
    }

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // 根据节点计算单价
    double calculateUnitPrice(HuffmanTreeNode<T> *node) {
        double area = calculateCircleArea(node->radius);
        return area / node->leafCount;
    }

    // 处理满足一定条件的节点添加到 result 和 collect 相关统计
    void processNode(int &collectNodes, int &collectNums, std::vector<TempNode<T>> &result, int level,
                     HuffmanTreeNode<T> *node) {
        collectNodes++;
        collectNums += node->leafCount;
        double collectionGuidelines = calculateUnitPrice(node);

        TempNode tempNode(level, collectionGuidelines, node->leafCount, node);
        result.push_back(tempNode);
    }

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    // 收集符合条件的内节点并计算单价再递增排序排序
    bool collectAndSortNodes(std::vector<TempNode<T>> &result, int min_leaf, int max_leaf, uint64_t DATASIZE,
                             std::ostream &os) {
        auto curRoot = getRoot();
        if (curRoot->isLeaf || curRoot == nullptr)
            return false;

        std::vector<HuffmanTreeNode<T> *> levelQueue;
        levelQueue.push_back(curRoot);
        int level = 0;   // 记录下降层级
        int collectNums = 0, collectNodes = 0;

        while (!levelQueue.empty()) {
            std::vector<HuffmanTreeNode<T> *> curLevel;

            for (HuffmanTreeNode<T> *levelNode: levelQueue) {

                if (levelNode->left) {
                    if (!levelNode->left->isLeaf) {
                        if (levelNode->left->leafCount > max_leaf) {
                            if (levelNode->left->left->isLeaf || levelNode->left->right->isLeaf) {
                                processNode(collectNodes, collectNums, result, level, levelNode->left);
                            } else {
                                curLevel.push_back(levelNode->left);
                            }
                        } else {
                            processNode(collectNodes, collectNums, result, level, levelNode->left);
                        }
                    }
                }

                if (levelNode->right) {
                    if (!levelNode->right->isLeaf) {
                        if (levelNode->right->leafCount > max_leaf) {
                            if (levelNode->right->left->isLeaf || levelNode->right->right->isLeaf) {
                                processNode(collectNodes, collectNums, result, level, levelNode->right);
                            } else {
                                curLevel.push_back(levelNode->right);
                            }
                        } else {
                            processNode(collectNodes, collectNums, result, level, levelNode->right);
                        }
                    }
                }

//                if (levelNode->left) {
//                    if (!levelNode->left->isLeaf) {
//                        if (levelNode->left->leafCount > max_leaf) {
//                            if (levelNode->left->left->isLeaf ||
//                                (!levelNode->left->left->isLeaf && levelNode->left->left->leafCount < min_leaf) ||
//                                levelNode->left->right->isLeaf ||
//                                (!levelNode->left->right->isLeaf && levelNode->left->right->leafCount < min_leaf)) {
//                                processNode(collectNodes, collectNums, result, level, levelNode->left);
//                            } else {
//                                curLevel.push_back(levelNode->left);
//                            }
//                        } else {
//                            processNode(collectNodes, collectNums, result, level, levelNode->left);
//                        }
//                    }
//                }
//
//                if (levelNode->right) {
//                    if (!levelNode->right->isLeaf) {
//                        if (levelNode->right->leafCount > max_leaf) {
//                            if (levelNode->right->left->isLeaf ||
//                                (!levelNode->right->left->isLeaf && levelNode->right->left->leafCount < min_leaf) ||
//                                levelNode->right->right->isLeaf ||
//                                (!levelNode->right->right->isLeaf && levelNode->right->right->leafCount < min_leaf)) {
//                                processNode(collectNodes, collectNums, result, level, levelNode->right);
//                            } else {
//                                curLevel.push_back(levelNode->right);
//                            }
//                        } else {
//                            processNode(collectNodes, collectNums, result, level, levelNode->right);
//                        }
//                    }
//                }

            }

            level++;
            levelQueue = curLevel;
        }

        os << "从上往下收集到的原数据点数量: 【" << collectNums << "】" << ",收集哈夫曼树内节点个数: 【" << collectNodes
           << "】" << std::endl;

        std::sort(result.begin(), result.end(), TempNode<T>::compareByGuidelines);

        return collectNums >= DATASIZE;
    }
};
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
